package leetCode.solution;

/**
 * 300. 最长递增子序列
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 * @author jerry
 * @ClassName:  longestIncreasingSubsequence_300   
 * @Description:TODO(描述这个类的作用)   
 * @date 2022年12月1日 下午4:39:57
 */
public class LongestIncreasingSubsequence_300 {
	public int lengthOfLIS(int[] nums) {
		if(nums==null || nums.length==0) {
			return 0;
		}
		int n = nums.length;
		int ends[] = new int[n]; // ends[i]:目前所有长度为i+1的递增子序列的最小结尾代表
		int right = 0;
		int maxLength = 1;
		ends[0]=nums[0];
		for(int i=0;i<n;i++) {
			int l = 0;
			int r = right;
			
			// l...r 范围找到>=nums[i]的最左侧位置
			while(l<=r) {
				int m = l+(r-l>>1);
				if(nums[i]>ends[m]) {
					l = m+1;
				}else {
					r = m-1;
				}
			}
			right = Math.max(right, l);
			ends[l] = nums[i];
			maxLength = Math.max(maxLength, l+1);
		}
		return maxLength;
	}
}
